package com.lh.arithmetic.sortarithmetic;

import java.util.Date;

import com.lh.log.log4j.LoggerImpl;
import com.lh.log.log4j.interfaces.Log;



/**
 ***************************************************************************** 
 ** Module : java冒泡排序算法
 ** 
 ** 思想:它是交换式排序算法的一种.将小的值"浮"到上面,将大的值"沈"到底部的一种排序方法.
 * n个元素的排序将进行n-1轮循环,在每一轮排序中相邻的元素进行比较,如果左边的小于或等于右边的,
 * 将保持原位置不变,如果左边的大于右边的,将这两个右边的元素的位置交换. 称定性:稳定的 时间复杂度:O(n2)
 ** 
 ** Date: 2011-12-19 Time: 上午10:16:11
 ** 
 ** Author: 李恒 (liheng)
 ** 
 ** (C) Copyright 2011 广州赢典信息科技有限公司
 ***************************************************************************** 
 */
public class BubbleUpSortArithmetic {
	 private static  Log logger = new LoggerImpl(BubbleUpSortArithmetic.class);
	/**
	 * 基本的冒泡排序法
	 * 
	 * @param oneDimensionalArray
	 * @return
	 * @Author: liheng
	 */
	/**
	 * 冒泡排序的过程很简单，首先将第一个记录的关键字与第 二个记录的关键字进行比较，若按升序排序，则当第一个记录的
	 * 关键字大于第二个记录的关键字时，将两个记录交换。然后再比 较第二个记录和第三个记录的关键字。依次类推，直至第n-1个
	 * 记录和第n个记录的关键字进行比较为止。通过这样的一趟冒 泡排序，结果使得关键字最大的记录被安置在最后一个记录的位
	 * 置上，即它的最终位置。接着进行第二趟冒泡排序，对前n-1个 记录进行同样的操作，其结果是使关键字次大的记录被安置到
	 * 倒数第二个位置上。这样，通过n一1趟冒泡排序，就将n-1个记 录安置到相应的最终位置上，剩下的关键字最小的记录就放在
	 * 第一个位置，从而实现了升序排序。
	 */
	public static int[] bubbleUpSortArithmeticBasic(int[] oneDimensionalArray) {
		// n个元素的数组进行n-1轮排序
		for (int i = 0; i < oneDimensionalArray.length - 1; i++) {
			// 因为每一轮循环将确定一个数组元素的位置,
			// 所以每一轮的比较次数将会递减
			for (int j = 0; j < oneDimensionalArray.length - i - 1; j++) { // 对当前无序区R[i..n]自上向下扫描
				// 如果第j个元素比它后面的相邻的元素j+1大的话就交换
				if (oneDimensionalArray[j] > oneDimensionalArray[j + 1]) {
					int temp = oneDimensionalArray[j];
					oneDimensionalArray[j] = oneDimensionalArray[j + 1];
					oneDimensionalArray[j + 1] = temp;
				}
			}
			printSortArray(oneDimensionalArray);

		}
		return oneDimensionalArray;
	}

	/**
	 * 第一种改进：不做无用功 设置一个标志位，当没有交换的时候这个标志位不会变化，那么说明数据已经
	 * 排序好了，就不需要再进行剩余的循环。只有在标志位被重新设置的情况下才会 进行剩余的循环。
	 */
	public static int[] bubbleUpSortArithmetic1(int[] oneDimensionalArray) {
		// n个元素的数组进行n-1轮排序
		boolean exchangeFlag;// 交换标志
		for (int i = 0; i < oneDimensionalArray.length - 1; i++) {
			// 因为每一轮循环将确定一个数组元素的位置,
			// 所以每一轮的比较次数将会递减
			exchangeFlag = false;
			for (int j = 0; j < oneDimensionalArray.length - i - 1; j++) { // 对当前无序区R[i..n]自上向下扫描
				// 如果第j个元素比它后面的相邻的元素j+1大的话就交换
				if (oneDimensionalArray[j] > oneDimensionalArray[j + 1]) {
					int temp = oneDimensionalArray[j];
					oneDimensionalArray[j] = oneDimensionalArray[j + 1];
					oneDimensionalArray[j + 1] = temp;
					exchangeFlag = true;// 发生了交换，故将交换标志置为真
				}
			}
			if (exchangeFlag) {// 发生了交换，输出
				printSortArray(oneDimensionalArray);
			}

			if (!exchangeFlag) {// 本趟排序未发生交换，提前终止算法
				return oneDimensionalArray;
			}
		}
		return oneDimensionalArray;
	}

	/**
	 * 第二种改进：记录犯罪现场 在冒泡排序中，每趟排序实现了将最大(升序)或 最小(降序)的记录安置到未排序部分的最后位置，即最终位置。
	 * 通过进一步观察研究，由于每趟排序过程中，通过和邻记录关键字两两 比较，大(升序)或小(降序)的记录在不断地往下沉或往后靠，
	 * 小(升序)或大(降序)的记录在不断往上冒或往前靠。 每经过一趟排序，在最后次交换位置后而的记录都已经排好序。根据
	 * 上面的思路，对n个记录进行第k趟排序，首先需在第k-1趟排 序时记下最后交换的位置。然后在第k趟排序时，将第一个记
	 * 录的关键字与第二个记录的关键字进行比较，符合交换条件时， 进行交换。再比较第二个记录和第三个记录的关键字，依次类
	 * 推，直至第m-1个记录和第m个记录的关键字进行比较，而不 需要比较至n-k-1个记录。在大部分排序中，m都小于n-k-1
	 * 从而减少了比较趟数和每趟的比较次数。由于在第一趟排序时， 没有上一趟排序的m值。因此，还要设置m的初始值为n-1。
	 */
	public static int[] bubbleUpSortArithmetic2(int[] oneDimensionalArray) {
		int m = oneDimensionalArray.length - 1;
		while (m > 0) {// m=0说明已经排到第一个元素
			int k = -1, j;
			for (j = 0; j < m; j++) {
				if (oneDimensionalArray[j] > oneDimensionalArray[j + 1]) {
					int temp = oneDimensionalArray[j];
					oneDimensionalArray[j] = oneDimensionalArray[j + 1];
					oneDimensionalArray[j + 1] = temp;
					k = j; // 记录每次交换的位置
				}
			}
			logger.debug("m=" + k);
			printSortArray(oneDimensionalArray);
			m = k; // 记录最后一个交换的位置

		}
		return oneDimensionalArray;
	}

	/**
	 * 第三种改进 双向扫描，一网打尽， 对n个记录进行排序时，设up记录了从前面向后面依次进行扫描时最后的交换位置，
	 * low记录了从后面向前面依次进行扫描时最前的交换位置。 由上个改进的冒泡排序的原理可知，up后面的记录和low前面的记录都已有序。
	 * 每趟排序都由两次不同方向的比较、交换组成。第一次是从未排好序的第一个记录开始， 即从low记录开始，向后依次两两比较，如果不符合条件，则交换之，
	 * 直至比较到未排好序的最后一个记录，即up记录为止。 同时记下最后一次交换的位置，并存于up。第二次是从未排好序的最后一个记录开始,
	 * 即从up记录开始，向前依次两两比较，如果不符合条件，则交换之， 直至比较到未排好序的第一个记录，即low记录为止。同时记下最后次交换的位置，
	 * 并存于low. 这样，就完成了一趟排序。 每趟排序都实现了将未排好序部分的关键字大的记录往后移(升序)，
	 * 关键字小的记录往前移（升序)，从而使两端已排好序（如果是降序，记录移动的方向则相反)。 未排好序部分的记录的首尾位置分别由low和up指明。
	 * 不断按上面的方法进行排序，使两端已排好序的记录不断增多， 未排好序部分的记录逐渐减少。即low和up的值不断接近，当low>=up时，
	 * 表明已没有未排好序的记录，排序就完成了。由于在第一趟排序时， 没有上趟排序的low和up值。因此，还要设置low和up的初始值分别为0和n-1。
	 */
	public static int[] bubbleUpSortArithmetic3(int[] oneDimensionalArray) {
		int low, up, index, i;
		low = 0;
		up = oneDimensionalArray.length - 1;
		index = low;
		while (up > low) {
			for (i = low; i < up; i++) { // 从上向下扫描
				if (oneDimensionalArray[i] > oneDimensionalArray[i + 1]) {
					int temp = oneDimensionalArray[i];
					oneDimensionalArray[i] = oneDimensionalArray[i + 1];
					oneDimensionalArray[i + 1] = temp;
					index = i;
				}
			}
			printSortArray(oneDimensionalArray);
			up = index; // 记录最后一个交换的位置
			for (i = up; i > low; i--) { // 从最后一个交换位置处从下向上扫描
				if (oneDimensionalArray[i - 1] > oneDimensionalArray[i]) {
					int temp = oneDimensionalArray[i - 1];
					oneDimensionalArray[i - 1] = oneDimensionalArray[i];
					oneDimensionalArray[i] = temp;
					index = i;
				}
			}
			printSortArray(oneDimensionalArray);
			low = index; // 记录最后一个交换的位置
		}
		return oneDimensionalArray;
	}

	/**
	 * 打印出数组的元素
	 * 
	 * @param arr
	 * @Author: liheng
	 */
	public static void printSortArray(int[] arr) {
		StringBuffer sb = new StringBuffer();
		for (int temp : arr) {
			sb.append(temp).append(",");
		}
		logger.debug(sb.substring(0, sb.length() - 1));
	}

	public static void main(String[] args) {
		// 测试冒泡排序法
		int[] arr = { 16, 18, 15, 20, 25, 30 };	
		System.out.println("基本的冒泡排序法开始。" + new Date());
		bubbleUpSortArithmeticBasic(arr);
		System.out.println("基本的冒泡排序法结束。" + new Date());
		System.out.println("改进的冒泡排序法1开始。" + new Date());
		int[] arr1 = { 16, 17, 18, 15, 20, 25, 30 };
		bubbleUpSortArithmetic1(arr1);
		System.out.println("改进的冒泡排序法1结束。" + new Date());
		System.out.println("改进的冒泡排序法2开始。" + new Date());
		int[] arr2 = { 16, 17, 18, 15, 20, 25, 30 };
		bubbleUpSortArithmetic2(arr2);
		System.out.println("改进的冒泡排序法2结束。" + new Date());
		System.out.println("改进的冒泡排序法3开始。" + new Date());
		int[] arr3 = { 16, 17, 18, 15, 20, 25, 30 ,5};
		bubbleUpSortArithmetic3(arr3);
		System.out.println("改进的冒泡排序法3结束。" + new Date());
	}

}
